/**
 * 
 */
package backtrack.passed2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class CombinationSum {
    /**
    Combination Sum
    Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

    The same repeated number may be chosen from C unlimited number of times.

    Note:

    All numbers (including target) will be positive integers.
    Elements in a combination (a1, a2, � , ak) must be in non-descending order. (ie, a1 ? a2 ? � ? ak).
    The solution set must not contain duplicate combinations.
    For example, given candidate set 2,3,6,7 and target 7, 
    A solution set is: 
    [7] 
    [2, 2, 3] 
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> solutions = new ArrayList<List<Integer>>();
        if (candidates != null && candidates.length != 0) {
            Arrays.sort(candidates);
            combinationSum1R0Helper(candidates, 0, target, new ArrayList<Integer>(), solutions);
        }
        
        return solutions;
    }
    
    private void combinationSum1R0Helper(int[] candidates, int level, int target, List<Integer> solution, List<List<Integer>> solutions) {
        if (target < 0)
            return;
        else if (target == 0) 
            solutions.add(new ArrayList<>(solution));
        else {
            for (int i = level; i < candidates.length; i++) {
                solution.add(candidates[i]);
                combinationSum1R0Helper(candidates, i, target - candidates[i], solution, solutions);
                solution.remove(solution.size() - 1);
            }   
        }
    }

    /**
    Combination Sum II
    Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

    Each number in C may only be used once in the combination.

    Note:

    All numbers (including target) will be positive integers.
    Elements in a combination (a1, a2, � , ak) must be in non-descending order. (ie, a1 ? a2 ? � ? ak).
    The solution set must not contain duplicate combinations.
    For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
    A solution set is: 
    [1, 7] 
    [1, 2, 5] 
    [2, 6] 
    [1, 1, 6] 
     */
    public List<List<Integer>> combinationSum2(int[] candidates,
            int target) {
        List<List<Integer>> solutions = new ArrayList<>();
        if (candidates != null && candidates.length > 0) {
            Arrays.sort(candidates);
            combinationSum2RHelper(candidates, target, 0, new ArrayList<Integer>(), solutions);
        }
        
        return solutions;
        
    } 
    
    private void combinationSum2RHelper(int[] candidates, int target, int level, List<Integer> cache, List<List<Integer>> solutions) {
        if (target == 0) {
            solutions.add(new ArrayList<>(cache));
        }
        else if (target < 0) {
            return;
        }
        else {
            for (int i = level; i < candidates.length; i++) {
                cache.add(candidates[i]);
                combinationSum2RHelper(candidates, target - candidates[i], i + 1, cache, solutions);
                cache.remove(cache.size() - 1);
                // pitfall to avoid duplication, like list [1, 1, 1, 2] and target 4, the solutions, [1, ,1 2] and [1, 1, , 2],
                // are duplicated. 
                while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
                    i++;
                }
            }
        }
    }

    /**
     * 
     */
    public CombinationSum() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();

        //		int[] candidates = new int[] { 10, 1, 2, 7, 6, 1, 5, 8 };
        //		int target = 8;

        int[] candidates = new int[] { 7 };
        int target = 7;

        List<List<Integer>> results = cs.combinationSum(candidates,
                target);
        cs.print(results);
    }

    private void print(List<List<Integer>> result) {
        System.out.printf("Total: %d\n", result.size());
        for (List<Integer> arr : result) {
            for (Integer i : arr) {
                System.out.printf("%d,", i);
            }
            System.out.println();
        }
    }

}
